package company.alibaba;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//关键的应该是合理的分配面粉数
//只需要记录消耗多少面粉，赚了多少钱
//1先统计每种种子最多可以包几个 只包一种粽子可以包max粽子数
//2组合这些可能的值，遍历出最大的数 1种子 1个 2种子 2个...... 这个时候只需要关心面粉够不够就可以
public class Alibaba2 {

    static int maxValue = 0;

    static ZhongZi[] zhongZis;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//n克面粉
        int m = sc.nextInt();//m种粽子
        int c = sc.nextInt();//n克面粉
        int d = sc.nextInt();//d价值
        zhongZis = new ZhongZi[m + 1];
        List<Integer> xianLiao = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            xianLiao.add(sc.nextInt());
            zhongZis[i] = new ZhongZi(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }
        xianLiao.add(Integer.MAX_VALUE);
        zhongZis[m] = new ZhongZi(c, 0, d);
        helper(m, xianLiao, 0);
        System.out.println(maxValue);
    }

    private static void helper(int m, List<Integer> list, int value) {
        boolean next = false;
        for (int i = 0; i < zhongZis.length; i++) {
            ZhongZi zi = zhongZis[i];
            if (m >= zi.getMianFeng() && list.get(i) >= zi.getXianLiao()) {
                List<Integer> copyList = new ArrayList<>(list);
                copyList.set(i, list.get(i) - zi.getXianLiao());
                helper(m - zi.getMianFeng(), copyList, value + zi.getValue());
                next = true;
            }
        }
        if (!next) {
            Math.max(maxValue, value);
        }
    }
}

class ZhongZi {
    private int mianFeng;
    private int xianLiao;
    private int value;

    public ZhongZi(int mianFeng, int xianLiao, int value) {
        this.mianFeng = mianFeng;
        this.xianLiao = xianLiao;
        this.value = value;
    }

    public int getMianFeng() {
        return mianFeng;
    }

    public void setMianFeng(int mianFeng) {
        this.mianFeng = mianFeng;
    }

    public int getXianLiao() {
        return xianLiao;
    }

    public void setXianLiao(int xianLiao) {
        this.xianLiao = xianLiao;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}
